#include <vector>
using namespace std;
class Solution {
    int gcd(int a, int b) {
        while (b!=0) {
            int c=a%b;
            a=b;
            b=c;
        }
        return a;
    }
public:
    int uniquePaths(int m, int n) {
        --m;
        --n;
        n=n+m;
        if (m*2>n) m=n-m;
        vector<int> f(m,0);
        for (int i=0;i<m;i++) f[i]=n-i;
        for (int i=2;i<=m;i++) {
            int a=i;
            for (int j=0;j<f.size() && a>1;j++) {
                int g=gcd(a, f[j]);
                a/=g;
                f[j]/=g;
            }
        }
        int ans=1;
        for (int i=0;i<f.size();i++) ans*=f[i];
        return ans;
    }
};
